package com.study.springboottest.leetcode;

import java.util.Arrays;

public class Test03 {

    public static void main(String[] args) {
        //暴力匹配测试
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int pos = match(text, pattern);
        System.out.println("匹配字符索引: " + pos);

        //KMP算法匹配测试
        String test = "ABAABC";
        System.out.println("test的next数组是" + Arrays.toString(computeNext(test)));
        String kmpText = "ABABDABACDABABCABAB";
        String kmpPattern = "ABABCABAB";
        int kmpPos = kmpMatch(kmpText, kmpPattern);
        System.out.println("KMP匹配字符索引: " + kmpPos);
    }

    /**
     * 在文本中查找模式的匹配位置
     *
     * @param text 待搜索的文本
     * @param pattern 搜索的模式
     * @return 模式在文本中首次出现的索引，如果未找到则返回-1
     */
    public static int match(String text, String pattern) {
        // 获取文本长度和模式长度
        int n = text.length();
        int m = pattern.length();

        // 遍历文本，检查每个可能的起始位置
        for (int i = 0; i <= n - m; i++) {
            // 初始化内部循环索引，用于逐字符比较
            int j;
            // 比较文本和模式的每个字符
            for (j = 0; j < m; j++) {
                // 如果字符不匹配，则跳出内部循环
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break;
                }
            }
            // 如果内部循环索引等于模式长度，表示找到匹配
            if (j == m) {
                // 返回匹配的起始位置索引
                return i;
            }
        }
        // 如果未找到匹配，返回-1
        return -1;
    }


    /**
     * 计算字符串匹配的 next 数组
     *
     * @param pattern 待匹配的字符串
     * @return 生成的 next 数组，用于优化字符串匹配过程
     */
    public static int[] computeNext(String pattern) {
        // m 为模式字符串的长度
        int m = pattern.length();
        // 初始化 next 数组，用于存储部分匹配信息
        int[] next = new int[m];
        // j 用于遍历模式字符串
        int j = 0;
        // k 用于比较字符是否相同
        int k = -1;
        // 初始化 next[0] 为 -1，因字符串为空时前一个字符不存在
        next[0] = -1;

        // 循环直到遍历完模式字符串
        while (j < m - 1) {
            // 当 k 为 -1 或当前字符相同，继续比较下一个字符
            if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
                // 移动到下一个字符
                j++;
                // 更新 k 的值
                k++;
                // 记录当前字符与前一个字符相同的情况
                next[j] = k;
            } else {
                // 当当前字符不同时，回溯 k 的值
                k = next[k];
            }
        }
        // 返回计算出的 next 数组
        return next;
    }

    /**
     * 使用KMP算法进行字符串匹配
     *
     * @param text    待搜索的文本字符串
     * @param pattern 待匹配的模式字符串
     * @return 如果匹配成功，返回模式字符串在文本字符串中的起始位置；否则返回-1
     */
    public static int kmpMatch(String text, String pattern) {
        // 文本字符串长度
        int n = text.length();
        // 模式字符串长度
        int m = pattern.length();
        // 计算模式字符串的next数组，用于优化匹配过程
        int[] next = computeNext(pattern);

        // 初始化文本串位置i和模式串位置j
        int i = 0;
        int j = 0;
        // 当i小于文本长度且j小于模式长度时，进行循环
        while (i < n && j < m) {
            // 当j为-1或当前字符匹配时，同时移动i和j
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                // 当当前字符不匹配时，根据next数组移动j，避免回溯
                j = next[j];
            }
        }
        // 如果j等于模式长度，表示匹配成功，返回匹配的起始位置
        if (j == m) {
            return i - j;
        } else {
            // 匹配失败，返回-1
            return -1;
        }
    }


}
